//package leetcode;
//
//
//import java.util.*;
//
//public class Main {
//
//
//    // dp[i] : i可以分成k份的种数
//    List<List<Integer>> res = new ArrayList<>();
//    Set<String> set = new HashSet<>();
//    public int divide(int n, int k) {
//
//        // write code here
//        dfs(n, 1, k, 0, new ArrayList<>());
//        return res.size();
//    }
//
//    public void dfs(int n, int pos, int k, int lastSum, ArrayList<Integer> track) {
//
//        if (track.size() == k - 1 && lastSum < n) {
//            StringBuilder sb = new StringBuilder();
//            for (int i = 0; i < track.size(); i++) {
//                sb.append(track.get(i));
//            }
//            sb.append(n - lastSum);
//            char[] chars = sb.toString().toCharArray();
//            Arrays.sort(chars);
//            if (set.add(new String(chars))) {
//                ArrayList<Integer> list = new ArrayList<>(track);
//                list.add(n - lastSum);
//                res.add(list);
//            }
//            return;
//        }
//        for (int i = pos; i < n; i++) {
//            if (lastSum + i > n || track.size() >= k - 1) {
//                break;
//            }
//            track.add(i);
//            dfs(n, i, k,lastSum + i,track);
//            track.remove(track.size() - 1);
//        }
//    }
//    public static void main(String[] args) {
//        Main main = new Main();
//        long l = System.currentTimeMillis();
//        System.out.println(main.divide(7, 3));
//        System.out.println(System.currentTimeMillis() - l);
//
//    }
//    public static int findBalancedIndex(int[] inputArray) {
//        // write code here
//        int n = inputArray.length;
//        // sums[i] : i前面的和（不包括i）
//        long[] sums = new long[n + 1];
//        sums[0] = 0;
//        for (int i = 1; i <= n; i++) {
//            sums[i] = sums[i-1] + inputArray[i - 1];
//        }
//
//        for (int i = 0; i < n; i++) {
//            if (sums[i + 1] == sums[n] - sums[i]) {
//                return i;
//            }
//        }
//        return -1;
//    }
//    // "<people><name>shopee</name></people>","people.age"
//    public static String GetXMLValue(String inxml, String path) {
//        // write code here
//        String s = inxml.replaceAll("><", ".").replaceAll("<", "");
//        String key = s.substring(0, s.indexOf('>'));
//        String value = s.substring(s.indexOf('>') + 1, s.indexOf('/'));
//        return key .equals( path) ? value : "";
//    }
//}
//
//import java.util.*;
//
//
//
//public class Solution {
//    /**
//     * Note: 类名、方法名、参数名已经指定，请勿修改
//     *
//     *
//     * 115 124 133 142 106
//     *  115 151 511
//     * @param n int整型 整数n
//     * @param k int整型 分为k份
//     * @return int整型
//     */
//    List<List<Integer>> res = new ArrayList<>();
//    public int divide(int n, int k) {
//
//        // write code here
//        dfs(n, 1, k, 0, new ArrayList<>());
//        return res.size();
//    }
//
//    public void dfs(int n, int pos, int k, int lastSum, ArrayList<Integer> track) {
//
//        if (track.size() == k && lastSum== n && !res.contains(track)) {
//            ArrayList<Integer> list = new ArrayList<>(track);
//            Collections.sort(list);
//            res.add(list);
//            return;
//        }
//        for (int i = pos; i < n; i++) {
//            if (lastSum + i > n || track.size() >= k) {
//                break;
//            }
//            track.add(i);
//            dfs(n, i, k,lastSum + i,track);
//            track.remove(track.size() - 1);
//        }
//    }
//}
